package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-29 16:50
 */
public class Q208 {
    class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }

        public void insert(String word) {
            TrieNode node = this;
            for (int i = 0; i < word.length(); i++) {
                int pos = word.charAt(i) - 'a';
                if (node.children[pos] == null) {
                    node.children[pos] = new TrieNode();
                }
                node = node.children[pos];
                if(i == word.length() - 1) {
                    node.isWord = true;
                }
            }
        }

        public TrieNode find(String word) {
            TrieNode node = this;
            for (int i = 0; i < word.length(); i++) {
                int pos = word.charAt(i) - 'a';
                if (node.children[pos] == null) {
                    return null;
                }
                node = node.children[pos];
            }
            return node;
        }

    }

    class Trie {

        TrieNode trieNode;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            trieNode = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            trieNode.insert(word);
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode node = trieNode.find(word);
            return node != null && node.isWord;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return trieNode.find(prefix) != null;
        }
    }
}
